package 剑指offer_leetcode;

import java.util.ArrayList;
import java.util.Arrays;

public class 剑指Offer38_字符串的排列 {
    public String[] permutation(String s) {
        char[] str = s.toCharArray();
        Arrays.sort(str);
        boolean[] vis=  new boolean[str.length];
        StringBuilder sb = new StringBuilder();
        ArrayList<String> res = new ArrayList<>();
        helper(res,str,vis,sb);
        String[] arr = new String[res.size()];
        for(int i=0;i<res.size();i++)
            arr[i] = res.get(i);
        return arr;
    }

    void helper(ArrayList res, char[] charStr, boolean[] vis, StringBuilder sb){
        if(sb.length()==charStr.length){
            res.add(new String(sb));
            return;
        }
        for(int i =0;i<charStr.length;i++){
            if(vis[i])
                continue;
            if(i>0 && charStr[i]==charStr[i-1] && !vis[i-1])
                continue;

            vis[i] = true;
            sb.append(charStr[i]);
            helper(res,charStr,vis,sb);
            vis[i] = false;
            sb.deleteCharAt(sb.length()-1);
        }
    }
}
